#include <iostream>
#include <vector>

using namespace std;
// 120. 三角形
// 给定一个三角形的数字阵列，选择一条自顶向下的路径，使得沿途的所有数字之和最小。（每一步只能移动到一个相邻的格子中。）

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
//        vector<int> mini = triangle[triangle.size()-1];
        vector<int> mini;
        for(int e:triangle[triangle.size()-1]) {
            mini.push_back(e);
        }
        int n = triangle[triangle.size()-1].size();

        for(int i = triangle.size() - 2; i >= 0; i--)
            for(int j = 0; j < triangle[i].size(); j++) {
//                int curLen = triangle[i].size();
//                if(j >= curLen) {
//                    triangle[i][j] = 0;
//                }
                mini[j] = min(mini[j], mini[j+1]) + triangle[i][j];
            }

        return mini[0];
    }
};

int main() {
    vector<vector<int>> triangle = { {2},
                                     {3, 4},
                                     {6,5,7},
                                     {4,1,8,3}};
    cout << Solution().minimumTotal(triangle) << endl;
    // 11
    return 0;
}
